Materi, Soal, dan Pembahasan – Operasi pada Graf dan Konsep Subgraf

Graf $A, B, D,$ dan $E$ keempatnya merupakan subgraf dari $G$ karena setiap simpul dan setiap sisinya termuat di $G$ sesuai definisi subgraf.  Sebaliknya, graf $C$ bukan subgraf dari $G$ karena graf $C$ memuat satu sisi tambahan (yang posisinya vertikal), padahal sisi itu tidak dimuat di $G.$
(Jawaban C)

Graf lengkap $K_2$ memiliki dua simpul dan satu sisi yang menghubungkan dua simpul tersebut. Tinjau dua kasus terkait banyak simpul yang dimiliki oleh subgrafnya.

1. Jika banyak simpul subgraf dari $K_2$ sama dengan $1,$ jelas hanya ada $2$ subgraf berbeda yang dapat dibuat, masing-masing merupakan graf trivial dengan menggunakan dua simpul yang berbeda.
2. Jika banyak simpul subgraf dari $K_2$ sama dengan $2,$ ada $2$ subgraf berbeda yang dapat dibuat, yaitu graf yang memuat dua simpul bertetangga dan graf yang memuat dua simpul yang sama, tetapi takbertetangga.

Jadi, secara keseluruhan, ada $\boxed{4}$ subgraf yang memuat setidaknya satu simpul dari graf lengkap $K_2.$
(Jawaban C)

Graf lengkap $K_3$ memiliki tiga simpul yang saling bertetangga. Tinjau tiga kasus terkait banyak simpul yang dimiliki oleh subgrafnya.

1. Jika banyak simpul subgraf dari $K_3$ sama dengan $1,$ jelas hanya ada $3$ subgraf berbeda yang dapat dibuat, masing-masing merupakan graf trivial dengan menggunakan tiga simpul yang berbeda.
2. Jika banyak simpul subgraf dari $K_3$ sama dengan $2,$ terdapat $C(3, 2) = \color{red}{3}$ cara memilih $2$ dari $3$ simpulnya dan ada $\color{red}{2}$ cara untuk memilih apakah dua simpul itu terhubung oleh sisi atau tidak. Jadi, ada $3 \times 2 = 6$ subgraf yang dapat dibuat.
3. Jika banyak simpul subgraf dari $K_3$ sama dengan $3,$ terdapat $2^3 = 8$ cara untuk memilih apakah setiap dua simpul terhubung oleh sisi atau tidak. Jadi, ada $8$ subgraf yang dapat dibuat.

Jadi, secara keseluruhan, ada $\boxed{3+6+8=17}$ subgraf yang memuat setidaknya satu simpul dari graf lengkap $K_3.$
(Jawaban C)

Dari model graf sederhana di atas, dapat ditinjau dua kasus berikut: (1) simpul $a$ dihilangkan dan (2) simpul $a$ tetap ada.

1. Jika simpul $a$ dihilangkan, semua sisi graf tersebut juga akan dihilangkan. Akibatnya, kita sekarang hanya memiliki tiga simpul untuk membuat subgraf. Banyak subgraf yang dapat dibuat dengan $1, 2,$ dan $3$ simpul berturut-turut adalah $3, 3,$ dan $1.$
2. Jika simpul $a$ tetap ada, maka untuk setiap simpul $x \in \{b, c, d\},$ kita dapat melakukan tiga tindakan berikut.
   
   1. 1. Simpul $x$ dan sisi $\{a, x\}$ tetap ada.
      2. Simpul $x$ tetap ada, tetapi sisi $\{a, x\}$ dihilangkan.
      3. Simpul $x$ dan sisi $\{a, x\}$ dihilangkan.

   Ini berarti ada $3^3 = 27$ subgraf yang dapat dibuat.

Jadi, secara keseluruhan, ada $\boxed{7 + 27 = 34}$ subgraf yang memuat setidaknya satu simpul dari graf sederhana tersebut.
(Jawaban C)

Subgraf merentang dari graf $Z$ adalah subgraf yang memuat semua simpul dari $Z.$ Ini berarti yang menentukan beda subgraf yang satu dengan subgraf yang lain adalah eksistensi sisinya. Kita punya dua pilihan pada masing-masing sisi, yaitu sisi itu tetap ada dalam subgraf atau dihilangkan. Karena ada $9$ sisi pada graf $Z,$ akan ada $2^{9} = 512$ kemungkinan terkait ada tidaknya sisi penghubung simpul. Dengan kata lain, ada $\boxed{512}$ subgraf merentang berbeda dari graf $Z.$
(Jawaban D)

Gabungan dari graf sederhana $G$ dan komplemennya, $\overline{G},$ adalah graf lengkap.
Karena $G$ memiliki $15$ sisi dan $\overline{G}$ memiliki $13$ sisi, gabungan kedua graf ini merupakan graf lengkap dengan $15+13 = 28$ sisi. Pada graf lengkap, hubungan banyak simpul $(v)$ dan sisinya $(e)$ dinyatakan oleh $e = \dfrac{v(v-1)}{2}.$ Karena $e = 28,$ diperoleh $v = 8.$ Jadi, banyak simpul pada $G$ (begitu juga dengan $\overline{G})$ adalah $\boxed{8}$
(Jawaban D)

Misalkan graf sederhana $G$ memiliki $v$ simpul dan $e$ sisi. Misalkan juga $\overline{G}$ memiliki $f$ sisi. Jika dua graf tersebut digabungkan, diperoleh graf lengkap dengan $v$ simpul dan $(e + f)$ sisi. Hubungan banyak simpul $(v)$ dan banyak sisinya $(e + f)$ dinyatakan oleh $$e + f = \dfrac{v(v-1)}{2}.$$Ini berarti $$f = \dfrac{v(v-1)}{2}-e.$$Jadi, banyak sisi pada $\overline{G}$ adalah $\boxed{\dfrac{v(v-1)}{2}-e}$
(Jawaban B)

Subgraf terinduksi simpul dibangun dari sejumlah simpul dari suatu graf beserta sisi penghubung simpul-simpul tersebut. Perhatikan bahwa subgraf dari $G$ pada gambar di atas bukan subgraf terinduksi simpul karena tidak ada sisi penghubung simpul $v_4$ dan $v_5.$  Jadi, agar diperoleh subgraf terinduksi simpul yang dibangun oleh simpul $v_1, v_2,$ $v_3, v_4,$ dan $v_5,$ dinotasikan $G[\{v_1, v_2, v_3, v_4, v_5\}],$ sisi yang perlu ditambahkan adalah sisi $v_4v_5.$
(Jawaban C)

Subgraf terinduksi simpul dari $G$ dibangun dari beberapa simpul $G$ dan sisi yang bersisian dengan setiap dua simpul tersebut. Klik adalah subgraf terinduksi simpul yang berupa graf lengkap, yaitu graf sederhana yang setiap simpulnya saling bertetangga. Perhatikan bahwa subgraf terinduksi simpul dari $G$ yang dibangun oleh tiga simpul $v_1, v_2,$ dan $v_6$ (membentuk seperti bangun segitiga) merupakan klik karena berupa graf lengkap dengan $3$ simpul. Subgraf terinduksi simpul yang diberikan pada opsi B, C, D, dan E tidak membentuk klik karena setidaknya ada dua simpul pembangunnya yang tidak bertetangga. Sebagai contoh, subgraf terinduksi simpul $G[\{v_1, v_3, v_5\}]$ tidak membentuk klik karena $v_1$ dan $v_3$ tidak bertetangga, begitu juga dengan $v_1$ dan $v_5.$
(Jawaban A)

$G$ merupakan graf sederhana yang memiliki $5$ simpul. Oleh karena itu, derajat maksimum yang dapat dicapai oleh suatu simpul adalah $5-1 = 4,$ yaitu ketika simpul tersebut bertetangga dengan setiap simpul lainnya. Tinjau simpul berderajat $3$ di $G,$ yang artinya simpul tersebut bertetangga dengan $3$ dari $4$ simpul yang ada (selain dirinya sendiri). Berdasarkan definisi graf komplemen, simpul tersebut hanya akan bertetangga dengan $4-3 = 1$ simpul yang tidak bertetangga dengannya di $G.$ Dengan cara yang serupa, kita akan memperoleh derajat simpul yang lain di $\overline{G},$ yaitu tiga simpul berderajat $4-2 = 2$ dan satu simpul berderajat $4-1=3.$ Dengan demikian, barisan derajat dari $\overline{G}$ (urutkan dari yang paling tinggi) adalah $(3, 2, 2, 2, 1).$
(Jawaban A)

Misalkan $G$ merupakan graf sederhana dengan $n$ simpul. Tinjau graf $G \cup \overline{G}.$ Himpunan simpulnya sama dengan himpunan simpul $G$ sesuai dengan definisi graf komplemen. Jika $u$ dan $v$ merupakan dua simpul berbeda sembarang dari $G \cup \overline{G},$ maka sisi penghubung $u$ dan $v$ berada di $G$ atau berdasarkan definisi graf komplemen, di $\overline{G}.$ Berdasarkan definisi gabungan himpunan, sisinya pasti di $G \cup \overline{G}.$ Oleh karena itu, setiap simpul terhubung satu sama lain oleh sisi. Dengan demikian, graf $G \cup \overline{G}$ merupakan graf lengkap $K_n.$ Jadi, proposisi tersebut terbukti benar. $\blacksquare$

Misalkan $G$ merupakan graf sederhana dengan $n$ simpul. Tinjau graf $G \cap \overline{G}.$ Himpunan simpulnya sama dengan himpunan simpul $G$ sesuai dengan definisi graf komplemen. Jika $u$ dan $v$ merupakan dua simpul berbeda sembarang dari $G \cap \overline{G}.$ maka sisi penghubung $u$ dan $v$ harus berada di $G$ dan $\overline{G}$ sekaligus. Namun, hal itu tidak mungkin terjadi karena bertentangan dengan definisi graf komplemen. Akibatnya, tidak ada satu pun sisi yang menghubungkan dua simpul di $G \cap \overline{G}.$ Dengan kata lain, $G \cap \overline{G}$ hanya memuat $n$ simpul tanpa ada sisi sehingga tergolong sebagai graf kosong.
Jadi, proposisi tersebut terbukti benar. $\blacksquare$

Jawaban a)
$K_n$ merupakan grup lengkap dengan $n$ simpul. Setiap simpul memiliki sisi pada setiap simpul lainnya. Akibatnya, setiap simpul di $\overline{G}$ tidak bertetangga dengan simpul apa pun. Ini berarti graf $\overline{G}$ merupakan graf kosong dengan $n$ simpul, yaitu graf yang hanya memuat $n$ simpul tanpa ada sisi sama sekali. Sebagai contoh, berikut diberikan model graf $K_6$ dan komplemennya.
Jawaban b)
$K_{m, n}$ merupakan graf bipartit lengkap yang himpunan simpulnya masing-masing memuat $m$ dan $n$ simpul. Setiap simpul pada satu himpunan bertetangga dengan setiap simpul pada himpunan lainnya dan tidak bertetangga dengan simpul pada himpunan yang sama. Akibatnya, simpul di $\overline{G}$ memiliki kriteria berikut: (1) setiap simpul pada himpunan yang sama saling bertetangga; (2) Tidak ada sisi yang menghubungkan simpul pada himpunan pertama ke simpul pada himpunan kedua. Sebagai contoh, berikut diberikan model graf $K_{2, 3}$ dan komplemennya.
Jawaban c)
$C_n$ merupakan siklus dengan $n$ simpul. Misalkan $v_1, v_2, \cdots, v_n$ merupakan simpul pembentuk siklus tersebut. Ini berarti $C_n = (v_1, v_2, \cdots, v_n, v_1)$ yang menyatakan bahwa simpul yang berdekatan berarti bertetangga. Pada graf komplemennya, setiap sisi menghubungkan simpul $v_i$ dan $v_j$ dengan $i \neq j + 1$ atau $i \ neq j-1$ untuk $1 \le i < j \le n.$ Sebagai contoh, berikut diberikan model graf $K_{2, 3}$ dan komplemennya.
Jawaban d)
$Q_n$ merupakan graf kubus dengan $2^n$ simpul. Dua simpul di $Q_n$ akan bertetangga jika untaian bit yang diwakilinya hanya berbeda satu bit pada posisi yang bersesuaian. Oleh karena itu, pada graf komplemennya, dinotasikan $\overline{Q_n},$ dua simpul akan bertetangga jika untaian bit yang diwakilinya berbeda lebih dari satu bit pada posisi yang bersesuaian.

Misalkan barisan derajat dari graf sederhana $G$ adalah $(d_1, d_2, \cdots, d_n).$ Karena $G$ memiliki $n$ simpul, derajat maksimum yang dapat dicapai adalah $n-1,$ yaitu ketika suatu simpul bertetangga dengan setiap simpul lainnya. Dengan demikian, derajat dari suatu simpul $v$ di $\overline{G}$ sama dengan $(n-1)$ dikurangi derajat simpul $v$ di $G$ sebagai akibat dari definisi graf komplemen. Perhatikan bahwa jika $d_i \ge d_j,$ haruslah berlaku $n-1-d_i \le n-1-d_j.$ Oleh karena itu, urutan barisan derajat tersebut harus dibalik dari belakang ke depan. Jadi, barisan derajat dari $\overline{G}$ adalah $$(n-1-d_n \mid n-1-d_{n-1} \mid \cdots \mid n-1-d_2 \mid n-1-d_1).$$Catatan: Tanda | dipakai sebagai pengganti tanda koma untuk mempermudah pembacaan notasi.